네트워크 그래프
확통, 이산수학, 벡터 / 네트워크 그래프
5.4 네트워크 그래프
점(노드)들과 이들을 잇는 선(간선)으로 구성되는 이산수학의 네트워크 그래프를 다룹니다.
무향 그래프 연결 연산자
평면기하의 선분 연산자는 하이픈이 두 개인 --이지만, 이산수학의 네트워크 간선 연산자는 반드시 하이픈이 세 개인 ---를 사용합니다. 이 연산자는 기하학적 직선이 아니라 두 정점 간의 위상수학적 연결 관계를 선언합니다.
graph: {
A --- B [weight="4"];
B --- C [weight="2"];
A --- C [weight="5"];
C --- D [weight="1"];
}, layout=spring대괄호 안에 weight= 속성을 적으면 간선의 정중앙에 가중치 숫자가 렌더링됩니다.
그래프 배치 알고리즘
네트워크 그래프는 사용자가 정점의 좌표를 일일이 지정하지 않고, 그래프 이론의 배치 알고리즘에 따라 자동으로 형태를 잡습니다.
첫째, 탄성 물리 모델인 layout=spring입니다.
연결된 간선을 스프링으로 간주하여 정점들이 서로 밀어내고 당기면서 가장 균형 잡힌 자연스러운 형태로 정점을 자동 분산 배치합니다. 복잡한 네트워크나 최단 경로 문제 도판에 적합합니다.
둘째, 원형 배치 모델인 layout=circular입니다.
모든 정점을 원 둘레 위에 일정한 간격으로 배치합니다. 완전 그래프나 해밀턴 경로 문제를 다룰 때 교차선이 대칭적으로 드러나도록 만들 때 유용합니다.
유향 그래프(방향 그래프) 표현
한쪽 방향으로만 진행하는 간선은 화살표가 포함된 --> 연산자를 사용합니다.
graph: {
S --> A [weight="3"];
S --> B [weight="2"];
A --> T [weight="4"];
B --> T [weight="1"];
}, layout=right출발점 S에서 도착점 T로 흐르는 네트워크 유량(Flow) 문제나 마르코프 연쇄의 상태 전이도를 작성할 때 방향성 화살표가 간선 중앙에 정확히 삽입됩니다.
---
### 예제
수능 및 모의고사 확률 단원에 단골로 출제되는 질병 진단 검사의 양성 판정 조건부 확률 문제를 수형도로 완벽하게 구현합니다.
@canvas: width=120mm, height=70mm, dpi=300
tree: {
root"전체 집단"
-> "유병자 $D$ (0.01)"
-> "양성 반응 $T^+$ (0.95)", "음성 반응 $T^-$ (0.05)";
root
-> "정상인 $D^c$ (0.99)"
-> "양성 반응 $T^+$ (0.02)", "음성 반응 $T^-$ (0.98)";
}, layout=right, level_dist=40mm, sibling_dist=12mm이 코드는 복잡한 좌표 지정 없이 단 8줄로 각 사건의 포함 관계와 조건부 확률 수치를 교재 출판 규격의 정갈한 수형도로 렌더링해 냅니다.